package cn.pugle.oj.leetcode;

import cn.pugle.oj.catalog.DynamicProblem;

/**
 * 编辑距离
 * see LC1143
 *
 * @author tzp
 * @since 2020/9/16
 */
public class LC72 implements DynamicProblem {
    public int minDistance(String word1, String word2) {
        if (word1.length() == 0) return word2.length();
        if (word2.length() == 0) return word1.length();
        int[][] state = new int[word1.length()][word2.length()];
        for (int i = word1.length() - 1; i >= 0; i--) {
            for (int j = word2.length() - 1; j >= 0; j--) {
                if (i == word1.length() - 1 && j == word2.length() - 1) {
                    state[i][j] = word1.charAt(i) == word2.charAt(j) ? 0 : 1;
                } else {
                    int min = Integer.MAX_VALUE;
                    //向下, delete word1多余的1个, 直接加1
                    if (i + 1 < word1.length()) {
                        min = Math.min(min, state[i + 1][j] + 1);
                    }//这里不需要else
                    //向右, insert word2少的那个, 直接加1
                    if (j + 1 < word2.length()) {
                        min = Math.min(min, state[i][j + 1] + 1);
                    }
                    //右下, replace, 判断不等加1
                    int thisPoint = word1.charAt(i) == word2.charAt(j) ? 0 : 1;
                    if (i + 1 < word1.length() && j + 1 < word2.length()) {
                        min = Math.min(min, state[i + 1][j + 1] + thisPoint);
                    } else {//右下为空时
                        if (i + 1 >= word1.length()) {//i超了
                            min = Math.min(min, word2.length() - j - 1 + thisPoint);
                        } else if (j + 1 >= word2.length()) {//j超了
                            min = Math.min(min, word1.length() - i - 1 + thisPoint);
                        } else {
                            throw new RuntimeException("???");
                        }
                    }
                    state[i][j] = min;
                }
            }
        }
        return state[0][0];
    }


    public static void main(String[] args) {
//        System.out.println(new LC72().minDistance("horse", "ros"));
//        System.out.println(new LC72().minDistance("abcdefg", "de"));
//        System.out.println(new LC72().minDistance("de", "abcdefg"));
        System.out.println(new LC72().minDistance("ab", "aob"));
    }
}
